//牛客 OR140 数列
//思路：1.按照公式将该数组完全赋值
//2.只需打印某位置上的数字即可

#include <stdio.h>
int main()
{
    int a[100000] = {1,2,0};
    for(int i = 2; i < 100000; i++)
    {
        a[i] = 2 * a[i-1] + a[i-2];
        a[i] %= 32767;//防止溢出
    } 

    int n = 0;
    scanf("%d", &n);
    while(n--)
    {
        int k = 0;
        scanf("%d", &k);
        printf("%d\n", a[k-1]);
    }
    return 0;
}